package JZ_Offer.dataStructure.queue_statck;

import java.util.Stack;

/**
 * 包含min函数的栈
 * <p>
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
 * <p>
 * 此栈包含的方法有：
 * push(value):将value压入栈中
 * pop():弹出栈顶元素
 * top():获取栈顶元素
 * min():获取栈中最小元素
 *
 * @Author piper
 * @Date 2019/12/19 9:43 上午
 */
public class JZ30_包含min函数的栈 {

    /**
     * 创建内部类 Node 作为一个单链表
     * head 变量记录栈顶节点
     * minValue 记录最小数字 每次pop、push更改
     */
    private static class MyStack {
        private Node head;
        private int minValue;

        private static class Node {
            Node next;
            int value;

            Node(int value) {
                this.value = value;
            }

            Node(int value, Node next) {
                this.value = value;
                this.next = next;
            }
        }

        public void push(int node) {
            if (head == null) {
                head = new Node(node);
                minValue = node;
            } else {
                head = new Node(node, head);
                // 插入元素比最小值小 就替换最小值
                minValue = minValue < node ? minValue : node;
            }
        }

        public void pop() {
            if (head == null) {
                return;
            }
            // 将头节点指向下个节点
            int headValue = head.value;
            head = head.next;
            // 如果移除的数字和最小值相等 就要寻找最小值了
            if (headValue == minValue) {
                Node n = head;
                // 没有节点了 重置最小值
                if (n == null) {
                    minValue = 0;
                    return;
                }

                // 将头节点值赋给最小值 依次和后面比较
                minValue = n.value;
                while (n != null) {
                    minValue = minValue < n.value ? minValue : n.value;
                    n = n.next;
                }
            }
        }

        public int top() {
            if (head != null) {
                return head.value;
            }
            return -1;
        }

        public int min() {
            return minValue;
        }
    }

    /**
     * 双栈法
     * 一个用来存所有的元素“stackTotal”,另一个用来存加入新的元素后当前stackTotal中对应的最小值。
     * 两个栈中的元素数量始终保持一致，当新的元素小于“stackLittle”栈顶元素时，“stackLittle”像栈顶push新来的元素，
     * 否则，“stackLittle”向栈顶加入原栈顶元素。
     * 执行“pop”方法时，两个栈同时弹出各自的栈顶元素
     */
    private static class MyStack1 {
        Stack<Integer> stackTotal = new Stack<Integer>();
        Stack<Integer> stackLittle = new Stack<Integer>();

        public void push(int node) {
            stackTotal.push(node);
            if (stackLittle.empty()) {
                stackLittle.push(node);
            } else {
                if (node <= stackLittle.peek()) {
                    stackLittle.push(node);
                } else {
                    stackLittle.push(stackLittle.peek());
                }
            }
        }

        public void pop() {
            stackTotal.pop();
            stackLittle.pop();
        }

        public int top() {
            return stackTotal.peek();
        }

        public int min() {
            return stackLittle.peek();
        }
    }


    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(3);
        System.out.println(stack.min());
        stack.push(4);
        System.out.println(stack.min());
        stack.push(2);
        System.out.println(stack.min());
        stack.push(3);
        System.out.println(stack.min());
        stack.pop();
        System.out.println(stack.min());
        stack.pop();
        System.out.println(stack.min());
        stack.pop();
        System.out.println(stack.min());
        stack.push(0);
        System.out.println(stack.min());
    }

}
